//
//  AlgorithmsTests.swift
//  AlgorithmsTests
//
//  Created by Archer on 2018/8/4.
//  Copyright © 2018年 Archer. All rights reserved.
//

import XCTest
@testable import Algorithms

class AlgorithmsTests: XCTestCase {
    
    /// 隔日默写 默默不敢忘
    
    func testQSort() {
        for _ in 0..<5 {
            var v = Array<Int>()
            for _ in 0..<1000 {
                v.append(Int(arc4random_uniform(10000)))
            }
            v._sort()
            XCTAssertTrue(v.isSorted)
        }
    }
    
    func testUniquify() {
        for _ in 0..<3 {
            var totalCount = 0
            var v = Array<Int>()
            for i in 0..<15 {
                var times = Int(arc4random_uniform(10))
                if times > 0 {
                    totalCount += (times - 1)
                }
                while times > 0 {
                    v.append(i)
                    times -= 1
                }
            }
            print("vector = \(v)")
            XCTAssertEqual(v.uniquify(), totalCount)
            print("vector = \(v)")
        }
    }
}
extension Array where Element: Comparable {
    
    mutating func uniquify() -> Int {
        if count < 2 { return 0 }
        let old = count
        var i = startIndex
        for j in 1..<endIndex {
            if self[i] != self[j] {
                i += 1
                self[i] = self[j]
            }
        }
        self = Array(self[startIndex...i])
        
        return old - i - 1
    }
    
    mutating func _sort() {
//        qsort(startIndex, endIndex)
        mergeSort(startIndex, endIndex)
    }
    
    
    var isSorted: Bool {
        for i in 1..<endIndex {
            if self[i - 1] > self[i] {
                return false
            }
        }
        return true
    }
    
    mutating func mergeSort(_ low: Index, _ high: Index) {
        if high - low < 2 { return }
        let mid = (high + low) >> 1
        mergeSort(low, mid)
        mergeSort(mid, high)
        _merge(low, mid, high)
    }
    
    mutating func _merge(_ low: Index, _ mid: Index, _ high: Index) {
        var copyPart = Array(self[low..<mid])
        var i = low, j = 0 , k = 0
        let fsize = copyPart.count
        let ssize = high - mid
        while j < fsize || k < ssize {
            if j < fsize && (k >= ssize || copyPart[j] <= self[mid + k]) {
                self[i] = copyPart[j]
                i += 1
                j += 1
            }
            if k < ssize && (j >= fsize || copyPart[j] > self[mid + k]) {
                self[i] = self[mid + k]
                i += 1
                k += 1
            }
        }
    }
    
    mutating func qsort(_ low: Index, _ high: Index) {
        if high - low < 2 { return }
        let pivotIdx = _partition(low, high)
        qsort(low, pivotIdx)
        qsort(pivotIdx + 1, high)
    }
    
    mutating func _partition(_ low: Index, _ high: Index) -> Index {
        let pivot = self[high - 1]
        var i = low
        for j in low..<(high - 1) {
            if self[j] <= pivot {
                (self[i], self[j]) = (self[j], self[i])
                i += 1
            }
        }
        (self[i], self[high - 1]) = (self[high - 1], self[i])
        return i
    }
}
